#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

#define MSG_SIZE 100

typedef struct {
    char data[MSG_SIZE];
    int index;
} Msg;

typedef struct Node {
    Msg msg;
    struct Node *next;
    struct Node *prev;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    int count;
    pthread_mutex_t mutex;
    pthread_cond_t front_cond;
    pthread_cond_t back_cond;
} Deque;

// 创建新节点
Node* createNode(const char *data, int index) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    strcpy(node->msg.data, data);
    node->msg.index = index;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

// 在队列前端插入节点
void insertFront(Deque *dq, Node *node) {
    pthread_mutex_lock(&dq->mutex);
    if (dq->head == NULL) {
        dq->head = dq->tail = node;
    } else {
        node->next = dq->head;
        dq->head->prev = node;
        dq->head = node;
    }
    dq->count++;
    pthread_cond_signal(&dq->front_cond);
    pthread_mutex_unlock(&dq->mutex);
}

// 在队列后端插入节点
void insertBack(Deque *dq, Node *node) {
    pthread_mutex_lock(&dq->mutex);
    if (dq->tail == NULL) {
        dq->head = dq->tail = node;
    } else {
        node->prev = dq->tail;
        dq->tail->next = node;
        dq->tail = node;
    }
    dq->count++;
    pthread_cond_signal(&dq->back_cond);
    pthread_mutex_unlock(&dq->mutex);
}

// 删除队列前端的节点
Node* removeFront(Deque *dq) {
    pthread_mutex_lock(&dq->mutex);
    Node *node = dq->head;
    if (node != NULL) {
        dq->head = node->next;
        if (dq->head != NULL) {
            dq->head->prev = NULL;
        } else {
            dq->tail = NULL;
        }
        dq->count--;
        pthread_cond_signal(&dq->back_cond);
    }
    pthread_mutex_unlock(&dq->mutex);
    return node;
}

// 删除队列后端的节点
Node* removeBack(Deque *dq) {
    pthread_mutex_lock(&dq->mutex);
    Node *node = dq->tail;
    if (node != NULL) {
        dq->tail = node->prev;
        if (dq->tail != NULL) {
            dq->tail->next = NULL;
        } else {
            dq->head = NULL;
        }
        dq->count--;
        pthread_cond_signal(&dq->front_cond);
    }
    pthread_mutex_unlock(&dq->mutex);
    return node;
}

// 生产者向队列前端插入消息
void* producerFront(void* arg) {
    Deque* dq = (Deque*)arg;
    int i = 0;
    while (i < 50) {
        Node *node = createNode(strcat("Front Message ", itoa(i, NULL, 10)), i);
        insertFront(dq, node);
        i++;
    }
    return NULL;
}

// 生产者向队列后端插入消息
void* producerBack(void* arg) {
    Deque* dq = (Deque*)arg;
    int i = 50;
    while (i < 100) {
        Node *node = createNode(strcat("Back Message ", itoa(i, NULL, 10)), i);
        insertBack(dq, node);
        i++;
    }
    return NULL;
}

// 消费者从队列前端获取消息并删除节点
void* consumerFront(void* arg) {
    Deque* dq = (Deque*)arg;
    while (1) {
        Node *node = removeFront(dq);
        if (node != NULL) {
            printf("Consumed Front: Message %d\n", node->msg.index);
            free(node);
        }
    }
    return NULL;
}

// 消费者从队列后端获取消息并删除节点
void* consumerBack(void* arg) {
    Deque* dq = (Deque*)arg;
    while (1) {
        Node *node = removeBack(dq);
        if (node != NULL) {
            printf("Consumed Back: Message %d\n", node->msg.index);
            free(node);
        }
    }
    return NULL;
}

int main() {
    Deque dq;
    dq.head = dq.tail = NULL;
    dq.count = 0;
    pthread_mutex_init(&dq.mutex, NULL);
    pthread_cond_init(&dq.front_cond, NULL);
    pthread_cond_init(&dq.back_cond, NULL);

    pthread_t prod_front_tid, prod_back_tid, cons_front_tid, cons_back_tid;
    pthread_create(&prod_front_tid, NULL, producerFront, &dq);
    pthread_create(&prod_back_tid, NULL, producerBack, &dq);
    pthread_create(&cons_front_tid, NULL, consumerFront, &dq);
    pthread_create(&cons_back_tid, NULL, consumerBack, &dq);

    pthread_join(prod_front_tid, NULL);
    pthread_join(prod_back_tid, NULL);
    pthread_cancel(cons_front_tid);
    pthread_cancel(cons_back_tid);

    pthread_mutex_destroy(&dq.mutex);
    pthread_cond_destroy(&dq.front_cond);
    pthread_cond_destroy(&dq.back_cond);

    return 0;
}